跳到主要内容

「NOIP 2022」建造军营

· 阅读需 4 分钟

分析一下题意，可以发现有一些关键边，他们是一定要看守的

而这个关键边的特性也很容易发现，就是如果这条边被去掉后该图不联通，这条边就是一定要看守的一条边，也就是关键的边，我们就要考虑能否只保留关键边

这时候聪明的小伙伴已经发现了：“欸主包主包，你说的那个关键的边不就是割边/桥吗”，于是我们就可以联想到边双缩点了

这时候我们就得到了一颗树，就可以考虑考虑树上DP了

设计DP数组为；f[u][0/1]f[u][0/1]，即以uu为根的子树中存在/不存在军营的情况

先思考初始值的设定：记每个强连通分量内的点数为point[i]，边数为edge[i]

f[u][0]=2edge[u]f[u][0]=2^{edge[u]}即任意选择边看守与否都不会影响军营的连通性，因为该节点内没有军营

f[u][1]=2edge[u]+point[u]−2edge[u]f[u][1]=2^{edge[u]+point[u]}-2^{edge[u]}，即任意选择建造军营与道路，然后容斥掉f[u][0]f[u][0]的情况

在思考树上DP的转移方程，设父亲为uu，儿子为vv

f[u][0]+=f[v][0]<<1f[u][0]+=f[v][0]<<1因为该子树上没有军营，所以这条割边也可以选择不看守

f[u][1]f[u][1]的转移较为复杂，要么是孩子没有建军营，该割边可不看守；如果建造了军营，那么点uu有无军营皆可，且该割边一定要看守

所以f[u][1]=f[u][1]∗(f[v][0]<<1)+f[u][1]∗f[v][1]+f[u][0]∗f[v][1]f[u][1]=f[u][1]*( f[v][0]<<1 )+f[u][1]*f[v][1]+f[u][0]*f[v][1]

再考虑如何统计答案，在已经确定的该子树合法且存在军营的情况下，子树外的边任意选择即可

一些实现细节代码见代码中的注释

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;

const int N=5e5+10, M=1e6+10, mod=1e9+7;

int cnt, num;
ll ans;
int dfn[N], low[N];
int group[N];
int point[N], edge[N];
ll pow2[N+M], siz[N];
ll f[N][2];
bool vis[N], bridge[M<<1];
vector< pii > rode[N];
vector< int > re_rode[N];  

void tarjan( int p,int ine )
{
	dfn[p]=low[p]=++cnt;
	for( auto &[x,iidx]:rode[p] )
	{
		if( iidx == ine ) continue;
		if( !dfn[x] )
		{
			tarjan( x,iidx^1 );
			low[p]=min( low[p],low[x] );
			if( low[x] > dfn[p] ) bridge[iidx]=bridge[iidx^1]=true;
		}
		else low[p]=min( low[p],dfn[x] );
	}
}

void get_group( int p )
{
	vis[p]=true;
	group[p]=num, point[num]++;
	for( auto &[x,iidx]:rode[p] )
	{
		if( vis[x] )       continue;
		if( bridge[iidx] ) continue;
		get_group( x );
	}
}

ll quick_power( ll a,ll b )
{
	ll ans=1;
	while( b > 0 )
	{
		if( b&1 ) ( ans*=a )%=mod;
		( a*=a )%=mod, b>>=1;
	}
	return ans;
}

void get_size( int p,int fa )
{
	siz[p]=edge[p];
	for( auto &x:re_rode[p] )
	{
		if( x == fa ) continue;
		get_size( x,p );
		siz[p]+=siz[x]+1;
	}
}

void tree_dp( int p,int fa )
{
	for( auto &x:re_rode[p] )
	{
		if( x == fa ) continue;
		tree_dp( x,p );
		( ( f[p][1]*=( f[x][0]<<1 )+f[x][1] )+=f[p][0]*f[x][1]%mod )%=mod;
		( f[p][0]*=( f[x][0]<<1 ) )%=mod;
	}
	( ans+=f[p][1]*pow2[max( siz[1]-siz[p]-1,0ll )] )%=mod;
}

int main()
{
	freopen( "barrack.in","r",stdin );
	freopen( "barrack.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n, m;
	cin>>n>>m;
	for( int i=1, u, v;i<=m;++i )
	{
		cin>>u>>v;
		rode[u].push_back( { v,i<<1 } );
		rode[v].push_back( { u,i<<1|1 } );
	}
	for( int i=1;i<=n;++i )
		if( !dfn[i] ) tarjan( i,0 );
	for( int i=1;i<=n;++i )
		if( !vis[i] ) ++num, get_group( i );
	for( int u=1;u<=n;++u )
		for( auto &[v,iidx]:rode[u] )
			if( group[u] != group[v] ) re_rode[group[u]].push_back( group[v] );
			else                       edge[group[u]]++;
	pow2[0]=1;
	for( int i=1;i<=n+m;i++ ) pow2[i]=pow2[i-1]*2%mod;//预处理2的幂数大概能少0.2s 
	for( int i=1;i<=num;++i )
	{
		edge[i]>>=1;//连接双向边，需要除以二 
		f[i][0]=pow2[edge[i]];
		f[i][1]=( ( pow2[edge[i]+point[i]]-f[i][0] )%mod+mod )%mod;
	}
	get_size( 1,0 );
	tree_dp( 1,0 );
	cout<<ans;
	QWQ
}